The Enigma Machine and the Way to Crack It

Rotor

Inside of a Rotor

The picture above is an image of the structure of the rotors. Every number on the ring represents a letter, and the green wires help us do the single letter substitution (e.g. After you input a letter A, Enigma will output a letter D).

Three Rotors.

We have three rotors in a line, and we can change the sequence of rotors (e.g. the third rotor in the first position and the first rotor in the second position, etc.). Everytime we input a letter, the leftmost rotor will rotate one position (e.g. input A will output E instead of D). After the leftmost rotor does a full rotation, the middle rotor will rotate one position, and after the middle rotor does a full rotation, the rightmost rotor will rotate for one position. So here we have \(26^3\) possible substitution for a single letter input.

Plugboard

Plugboard.

The plugboard is a very powerful part of the Enigma machine. We can connect two letters in the keyboard using a wire and thus swap the two letters during the encoding process. For example, in the picture, we have A connected to J, so every time A is pressed in the keyboard, the letter A will be transferred into J first and then encoded by the machine.

Setting

This is a key sheet.

The leftmost column in the key sheet tells us the sequence of the rotors, the second column tells us the initial letter on the rotor rings, and the third column tells all the plugboard pairs.

Reflector

The reflector is another important part in the Enigma machine. It makes the encoding process self-reversible, which makes the machine not only an encipher, but also a decipher, given the exactly same setting. For example, after you set up the machine according to the daily key, typing A will give you the encoded letter E, and typing E will give you the decoded letter A. Also, the reflector is a trick to make sure the input messages will not be encoded as itself, because in the reflector every letter is connected to the letter other than itself by a wire. But this characteristic turned out to be a leak for the enigma machine, since it will reduce the possibility by a large amount.

Encoding Process

Here is a process diagram for encoding a letter in the Enigma machine. We type letter T in the keyboard, and the signal will go through the plugboard, be changed into K, and go through the three rotors one by one. When the signal arrives at the reflector, it will be connected to another fixed joint. The signal which comes out from the reflector will go through the same process with opposite direction and, finally, G in the lightboard will light up. Self-reversible means given exactly same setting, if you type G in the keyboard, T will light up in the lightboard. That is how you decipher the secret intelligence.

Substitution Function

The first thing to crack the Enigma is to figure out the daily key. The polish took advantage of a mathematical method called the substitution function. Suppose the message key is XYZ, and after encoding (typing twice) it becomes HGABLE. Therefore, we can get a series of equations \[X(A0)=H\] \[Y(A1)=G\] \[Z(A2)=A\] \[X(A3)=B\] \[Y(A4)=L\] \[Z(A5)=E\] where A0, A1, …, A5 are the subsitution functions that map the input letter to the output letter on the right. Since the enigma is self-reversible, we can say that \[X(A0)(A0)=X\] Plugging this property in the 4th equation above, we get \[X(A0)(A0)(A3)=B\] Then we can replace \(X(A0)\) with \(H\), as shown in the 1st equation. We get \[H(A0)(A3)=B\]

We notice that X disappeared. The final equation left us with no letter from the message key, which tells us that on this particular day, \(H\) is turned into \(B\) using the substitution function \((A0)(A3)\). Therefore, we know that \((A0)(A3)\) is the substitution function for this day.

Knowing the daily key and substitution function, we may think it’s possible to violently crack the machine by trying all the possibilities of the initial rotor setting and see which setting gives us the substitution function \((A0)(A3)\). But this is only possible without the existence of the plugboard, and it will only take about 3 hours, using 100 enigma, 100 people, and 10 seconds per try. However, the plugboard enlarges the possibility by 100,391,791,500, so there must be a way to eliminate the effect of the plugboard, which Rejeweski actually accomplished in a smart way.

Cycle Group

Rajeweski found an important property between the plain text and the encoded text, the cycle group. See below, suppose the first line denotes plain text and the second line is the encoded text \[A B C D E F G H\] \[C H E F A B D G\] The cycle groups for the above relationship are therefore \((A, C, E)\) and \((B, H, G, D, F)\) Notice that A from plain text encodes to C, and C from plain text encodes to E, then E encodes back to A, so this constructs a cycle group, similar for \((B, H, G, D, F)\).

An important feature of the cycle group is called “links.” Links are the lengths of the cycle group. For example \((A, C, E)\) has link of 3, and \((B, H, G, D, F)\) has link of 5. Suppose that from the substitution function \((A0)(A3)\), we get a matching relationship similar to the example above, so that each letter is mapped to another. Then we can figure out the cycle groups of \((A0)(A3)\), let’s say thay are \[(A, C, M, Y, N, Z, Q, D, P, D, O) (E, U, I, S, G) (F, T, H, R) (J, V) (K, W) (L, X)\] where they have links of 11, 5, 4, 2, 2, 2, respectively. The Polish then took advantage of the leak of the plugboard, which is that a wire swaps a pair of letters. They found that swapping any two letters in the cycle groups will not change the links of the cycle groups, hence the links are unique to a set of cycle groups. So once we have the information about cycle groups and their links, we no longer consider the effect of the plugboard because it doesn’t change our result. Thus, we get rid of the plugboard.

Cracking Process

The Polish spent one year to sort the links of the cycle groups according to the initial setting of the Enigma. Specifically, they matched each set of links to several possible initial settings, and constructed a catalogue for those information. To crack the machine, first, they use the first 6 keys to find out the substitution functions as well as the cycle groups, then they have the information of the links, then they can at least know the range of initial rotor settings they can try by referring to the catalogue. After that, they tried all the possible initial settings and violently cracked, so that they got the initial setting of the rotors.

The arrangement of the plugboard is also essential in the deciphering process. To crack the plugboard, they first set up the Enigma using the initial rotor setting they figured out from above, then without plugging in the plugboard, they input some enciphered message and see how the letters are swapped. This makes use of relatively simple encryption, so it’s easy to figure out which 6 pairs of letters are swapped. So far, the Polish have all the initial settings of the Enigma, and are thus ready to decode any encoded messages from Germany.